import java.util.Arrays;

public class MinMoney {
    // 兑换零钱
    // https://www.nowcoder.com/practice/3911a20b3f8743058214ceaa099eeb45?tpId=295&tags=&title=&difficulty=0&judgeStatus=0&rp=0&sourceUrl=%2Fexam%2Foj%3FquestionJobId%3D10%26subTabName%3Donline_coding_page
    public int minMoney (int[] arr, int aim) {
        // write code here
        // 完全背包问题
        // dp[i][j]表示从前i个货币中选择装入，使得背包中的货币数目恰好为j的最少张数
        int[][] dp = new int[arr.length+1][aim+1];
        // 初始化
        int INF = 0x3f3f3f3f;
        for (int j = 1; j <= aim; j++) {
            // 从前0个货币中选择装入，使得背包中的钱币总额为j，无法满足
            dp[0][j] = INF;
        }
        for (int i = 1; i <= arr.length; i++) {
            for (int j = 0; j <= aim; j++) {
                dp[i][j] = dp[i-1][j];
                if (j >= arr[i-1] && dp[i][j-arr[i-1]] != INF) {
                    dp[i][j] = Math.min(dp[i][j], dp[i][j-arr[i-1]] + 1);
                }
            }
        }
        return dp[arr.length][aim] == INF ? -1 : dp[arr.length][aim];
    }

    /**
     * 空间优化
     * @param arr
     * @param aim
     * @return
     */
    public int minMoney1 (int[] arr, int aim) {
        // write code here
        // 完全背包问题
        // dp[i][j]表示从前i个货币中选择装入，使得背包中的货币数目恰好为j的最少张数
        int[] dp = new int[aim + 1];
        // 初始化
        int INF = 0x3f3f3f3f;
        for (int j = 1; j <= aim; j++) {
            // 从前0个货币中选择装入，使得背包中的钱币总额为j，无法满足
            dp[j] = INF;
        }
        for (int i = 1; i <= arr.length; i++) {
            for (int j = arr[i-1]; j <= aim; j++) {
                dp[j] = Math.min(dp[j], dp[j - arr[i - 1]] + 1);
            }
        }
        return dp[aim] == INF ? -1 : dp[aim];
    }

    public static void main(String[] args) {
        MinMoney minMoney = new MinMoney();
        System.out.println(minMoney.minMoney(new int[]{357,322,318,181,22,158,365}, 4976));
    }
}
